# JZ4 重建二叉树
# 描述
# 给定某二叉树的前序遍历和中序遍历，请重建出该二叉树并返回它的头结点。
# 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出如下图所示。
# 提示:
# 1.0 <= pre.length <= 2000
# 2.vin.length == pre.length
# 3.-10000 <= pre[i], vin[i] <= 10000
# 4.pre 和 vin 均无重复元素
# 5.vin出现的元素均出现在 pre里
# 6.只需要返回根结点，系统会自动输出整颗树做答案对比
#
# 示例1
# 输入：
# [1,2,4,7,3,5,6,8],[4,7,2,1,5,3,8,6]
# 返回值：
# {1,2,3,4,#,5,6,#,7,#,#,8}
# 说明：
# 返回根节点，系统会输出整颗二叉树对比结果
# 示例2
# 输入：
# [1],[1]
# 返回值：
# {1}
# 示例3
# 输入：
# [1,2,3,4,5,6,7],[3,2,4,1,6,5,7]
# 返回值：
# {1,2,5,3,4,6,7}

# -*- coding:utf-8 -*-
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

# 核心代码模式
class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, vin):
        # write code here
        # 前序遍历第一个数就是根，是中序遍历中间位置的数
        # 中序遍历中间数左边是左子树，右边同理
        # 按照中序中间数分左右两块，再重复上述步骤
        # 重复的动作用递归

        # 先判断二叉树是否为空
        if not pre:
            return None
        # 先找前序根值及中序根位置
        root = TreeNode(pre[0])
        mid = vin.index(pre[0])
        # 递归构造左右子树
        # 左子树 前序根后前面一部分，中序tin中间值左边
        # mid+1 是因为前序中根在首位且pyton[]区间左闭右开
        # 别忘了 root.left/right  self.
        root.left = self.reConstructBinaryTree(pre[1:mid + 1], vin[:mid])
        # 右子树同理
        root.right = self.reConstructBinaryTree(pre[mid + 1:], vin[mid + 1:])
        return root